package com.mlamp;

import java.util.*;

/**
 * 给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。
 * <p>
 * 1. 如何判断一个树是不是有效的，第一点是树上没有环；
 * 其节点数和边的数量都是 n - 1 = edges 的关系
 * 我们还需要判断连通性，也就是说从一个节点出发，可以遍历到所有的点，满足这两个条件的图才能算是树
 */
public class 以图判树 {

    public static void main(String[] args) {

    }


    public boolean validTree(int n, int[][] edges) {
        if (n - 1 != edges.length) return false;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        buildGraph(graph, edges, n);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (!visited.add(cur)) return false;
            for (int nei : graph.get(cur)) {
                queue.offer(nei);
                graph.get(nei).remove(cur);
            }
        }
        return visited.size() == n;
    }


    public boolean isvalid(int n, int[][] edges) {
        if (n - 1 != edges.length) return false;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        buildGraph(graph, edges, n);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (!visited.add(cur)) return false;
            for (int nei : graph.get(cur)) {
                queue.offer(nei);
                graph.get(nei).remove(cur);
            }
        }
        return visited.size() == n;
    }


    public boolean validTree2(int n, int[][] edges) {
        if (n - 1 != edges.length) return false;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        buildGraph2(graph, edges, n);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (!visited.add(cur)) return false;
            for (int nei : graph.get(cur)) {
                queue.offer(nei);
                graph.get(nei).remove(cur);
            }
        }
        return visited.size() == n;
    }


    private void buildGraph2(Map<Integer, Set<Integer>> graph, int[][] edges, int n) {
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }


    private void buildGraph(Map<Integer, Set<Integer>> graph, int[][] edges, int n) {
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<Integer>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }


}
